package first.niuke.simple;

import java.util.*;

/**
 * @ClassName NC46
 * @description:
 * @author: 荣燊
 * @create: 2021-04-13 10:28
 **/
public class NC46 {
    public static void main(String[] args) {
        int[] a = {100, 10, 20, 70, 60, 10, 50};
        Arrays.sort(a);
        for (int i : a) {
            System.out.println(i);
        }

    }


    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        ArrayList<Integer> arrayList = new ArrayList<>();

        if (num.length == 0 || target == 0 || num==null) {
            return list;
        }

        Arrays.sort(num); //从小到大排序
        dfs(num, target, list, arrayList, 0);
        return list;
    }

    public void dfs(int[] num, int target, ArrayList<ArrayList<Integer>> list,
                    ArrayList<Integer> arrayList, int start) {
        //递归结束
        if (target == 0) {
            list.add(arrayList);
            return;
        }

        for (int i=start; i<num.length; i++) {

            if (num[i] <= target) {
                arrayList.add(num[i]);
                dfs(num, target-num[i], list, arrayList, i+1); //递归会将
                //上面如果递归错误，证明target<num[i],这时就要把之前加入的去掉
                arrayList.remove(arrayList.size()-1);
            }

        }
        return;
    }
}
